package window;

import java.util.*;

public class Ex76 {
    static class Solution {
        public String minWindow1(String s, String t) {
            Map<Character, Integer> map = new HashMap<>();
            int m = s.length(), n = t.length(), needCount = 0, res = Integer.MAX_VALUE;
            String resStr = null;
            for (int i = 0; i < n; i++) {
                char c = t.charAt(i);
                if (map.containsKey(c)) map.put(c, map.get(c) + 1);
                else map.put(c, 1);
                needCount++;
            }
            int lo = 0, hi = 0;
           loop: while (hi < m) {
                //将lo移动到需要数字的位置
                char sl = s.charAt(lo);
                while (lo < m && (!map.containsKey(sl) || map.get(sl) < 0)) {
                    if (map.containsKey(sl) && map.get(sl) < 0) {
                        map.put(sl, map.get(sl) + 1);
                    }
                    lo++;
                    if (lo == m) break loop;
                    sl = s.charAt(lo);
                }
                if (hi == 0) hi = lo;
                while (needCount > 0 && hi < m) {
                    char c = s.charAt(hi);
                    if (!map.containsKey(c)) {
                        //不包含，说明是不需要的数字
                        map.put(c, -1);
                    } else {
                        //无论需不需要当前数字，都需要将value - 1
                        int temp = map.get(c);
                        map.put(c, temp - 1);
                        if (temp > 0) {
                            needCount--;
                            if (needCount == 0) {
                                if (hi - lo + 1 < res) {
                                    res = hi - lo + 1;
                                    resStr = s.substring(lo, hi + 1);
                                } 
                                break;
                            }
                        }
                    } 
                    hi++;
                }
                map.put(s.charAt(lo), map.get(s.charAt(lo)) + 1);
                lo++;
                needCount++;
            }
            return resStr;
        }

        public String minWindow(String s, String t) {
            int m = s.length(), n = t.length(), needCount = 0, res = Integer.MAX_VALUE;
            String resStr = "";
            //由于字符只有128个，完全可以通过一个数组表示字典
            //这样做的好处是还不用频繁判断是否存在，是否 < 0,无脑加1就行了
            int[] dic = new int[128];
            for (int i = 0; i < n; i++) {
                dic[t.charAt(i)] += 1;
            }
            int lo = 0, hi = 0;

            //放了一个错误，老是先动lo再考虑hi，实际上应该先动hi，保证窗口的存在
            while (hi < m) {
               char c = s.charAt(hi);
               if (dic[c] > 0) needCount--;
               dic[c]--;
               if (needCount == 0) {
                  while (lo < hi && dic[s.charAt(lo)] <= 0) {
                      dic[s.charAt(lo)]++;
                      lo++;
                  }
                  if (hi - lo + 1 < res) {
                      res = hi - lo + 1;
                      resStr = s.substring(lo, hi + 1);
                  }
                  needCount++;
                  dic[s.charAt(lo)]++;
                  lo++;
               }
               hi++;
            }
            return resStr;
        }
    }  

    public static void main(String[] args) {
        Solution s = new Solution();
        String res = s.minWindow("ADOBECODEBANC", "ABC");
        System.out.println(res);
    }
}


/* 

                if (!map.containsKey(c)) {
                    //不包含，说明是不需要的数字
                    map.put(c, -1);
                } else {
                    //无论需不需要当前数字，都需要将value - 1
                    int temp = map.get(c);
                    map.put(c, temp - 1);
                    if (temp > 0) {
                        needCount--;
                        
                    }
                } 



*/